昨天之前介紹了這次我會使用到的工具，分別是Go-ethereum跟gnark，而當我們熟悉好工具之後，便可以開始我們的ZK Rollup實作了，而在實作的過程中，我們必須得要定義好我們的資料結構，我需要定義好我們的帳號樹(account tree)以及交易樹(batch tree)，這兩個是用雜湊樹的方式來實作，也因此我們可以只透過儲存根雜湊值來做鏈上存證，之所以使用雜湊樹的資料結構，是因為驗證某個節點存在，時間複雜度只需要，可以加快我們產生證明的時間，而跟雜湊樹相關的特性，如果不太清楚的人可以上網搜尋相關文章，關鍵字可以下merkle tree去進行搜尋，在這邊就不做深入的探討，接下來來定義我的資料結構吧！
帳號樹是用來儲存鏈下所有使用者的狀態，裡面應該要能表示使用者的nonce與餘額，這邊之所以用nonce是要防止重放攻擊(replay attack)，除此之外，這邊我還需要識別每個使用者，所以還要能表示不同的使用者，於是在帳號樹最底下的葉節點，儲存的便是該帳戶的公鑰、餘額與nonce的雜湊，而這邊的公鑰，我希望能用來驗證使用者傳給我的交易資訊的簽章，由於這是要含在證明裡面的，我又不希望他上鏈，所以可以用之前所說的ZK-friendly的簽章演算法來做，我在這邊選用的是EdDSA簽章方式，而EdDSA的公鑰是一個點，他有他的X跟Y數值，所以我的葉節點定義如下：
所以由這些葉節點組出的雜湊樹便是我鏈下的帳號樹，透過他便可以明確的表示我鏈下所有使用者帳戶的狀態。
每次打包交易上鏈，都必須說明在這次打包的過程中，我包了哪些交易，所以這時候可以透過雜湊樹的資料結構，將打包的交易資料弄成一個雜湊樹，透過公開根雜湊值，來一次表達這次打包的交易，除此之外我們還得要定義鏈下交易的格式，以下是我對鏈下交易的包含資料：
這邊是鏈下使用者要進行交易時，傳給打包交易的人的資料，而打包的人要負責驗證送過來的交易資料合法性，確認過後才將這筆交易資料打包進去，每次要打包的交易數量就是要將交易樹的葉節點填滿為止，而這時候其實交易樹的葉節點也顯而易見，便是拿使用者送過來的交易資訊去除簽章後取雜湊，便是這個交易樹的葉節點，因此對交易樹的葉節點定義如下：
所以由這些葉節點組出的交易樹便可以很好的表示出我這次要打包的交易有哪些。
之前說到ZK Rollup就是透過上傳證明來驗證出打包上鏈的交易都是合法的，因此我們必須要寫出一個驗證我們傳上去的帳號樹與交易樹的根雜湊值都是正確的，所以我們輸入除了帶新舊的根雜湊值，還得要帶入交易樹的根雜湊值變化，必須得要驗證每一次的變化都是正確的，所以新的交易樹的根雜湊值才會是正確的，因此這個電路的輸入基本上就很明顯是以下幾個：
而每次要驗證的的東西如下：
透過以上的說明，就可以建立出我們要證明的電路了！
程式碼如下：
import (
cryptoTwistededwards "github.com/consensys/gnark-crypto/ecc/twistededwards"
"github.com/consensys/gnark/frontend"
"github.com/consensys/gnark/std/algebra/twistededwards"
"github.com/consensys/gnark/std/hash/mimc"
"github.com/consensys/gnark/std/signature/eddsa"
)
const (
AccountTreeHeight = 帳號樹樹高
BatchTreeHeight = 交易樹樹高
BatchSize = 1 << BatchTreeHeight
)
type Account struct {
PublicKeyX frontend.Variable `gnark:"publicKeyX"`
PublicKeyY frontend.Variable `gnark:"publicKeyY"`
Balance frontend.Variable `gnark:"balance"`
Nonce frontend.Variable `gnark:"nonce"`
}
type Batch struct {
Sender frontend.Variable `gnark:"sender"`
Receiver frontend.Variable `gnark:"receiver"`
Amount frontend.Variable `gnark:"amount"`
Nonce frontend.Variable `gnark:"nonce"`
Signature eddsa.Signature `gnark:"signature"`
SenderBefore Account
SenderAfter Account
SenderMerkleProof [AccountTreeHeight]frontend.Variable `gnark:"senderMerkleProof"`
ReceiverBefore Account
ReceiverAfter Account
ReceiverMerkleProof [AccountTreeHeight]frontend.Variable `gnark:"receiverMerkleProof"`
}
// 驗證交易內容合法
func (batch *Batch) Transfer(api frontend.API) frontend.Variable {
var check frontend.Variable = 1
var one frontend.Variable = 1
api.AssertIsEqual(check, api.IsZero(api.Cmp(batch.SenderBefore.PublicKeyX, batch.SenderAfter.PublicKeyX)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(batch.SenderBefore.PublicKeyY, batch.SenderAfter.PublicKeyY)))
api.AssertIsEqual(check, api.Or(api.IsZero(api.Cmp(api.Cmp(batch.SenderBefore.Balance, batch.Amount), one)), api.IsZero(api.Cmp(batch.SenderBefore.Balance, batch.Amount))))
api.AssertIsEqual(check, api.IsZero(api.Cmp(api.Add(batch.SenderAfter.Balance, batch.Amount), batch.SenderBefore.Balance)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(batch.SenderBefore.Nonce, batch.Nonce)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(api.Add(batch.Nonce, one), batch.SenderAfter.Nonce)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(batch.ReceiverBefore.PublicKeyX, batch.ReceiverAfter.PublicKeyX)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(batch.ReceiverBefore.PublicKeyY, batch.ReceiverAfter.PublicKeyY)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(api.Add(batch.ReceiverBefore.Balance, batch.Amount), batch.ReceiverAfter.Balance)))
api.AssertIsEqual(check, api.IsZero(api.Cmp(batch.ReceiverBefore.Nonce, batch.ReceiverAfter.Nonce)))
return check
}
func (batch *Batch) Message(mimcHash *mimc.MiMC) frontend.Variable {
mimcHash.Reset()
mimcHash.Write(batch.Sender, batch.Receiver, batch.Amount, batch.Nonce)
msg := mimcHash.Sum()
mimcHash.Reset()
return msg
}
type RollupCircuit struct {
AccountRootBefore frontend.Variable `gnark:"accountRootBefore,public"`
AccountRootAfter frontend.Variable `gnark:"accountRootAfter,public"`
AccountRootFlow [BatchSize*2 + 1]frontend.Variable `gnark:"accountRootFlow"`
BatchRoot frontend.Variable `gnark:"batchRoot,public"`
Batches [BatchSize]Batch
}
func (circuit *RollupCircuit) Define(api frontend.API) error {
var one frontend.Variable = 1
mimcHash, err := mimc.NewMiMC(api)
if err != nil {
return err
}
curve, err := twistededwards.NewEdCurve(api, cryptoTwistededwards.BN254)
if err != nil {
return err
}
batchTreeNode := []frontend.Variable{}
for i := 0; i < BatchSize; i++ {
api.AssertIsEqual(circuit.Batches[i].Transfer(api), one)
verifyMerkleProof(api, circuit.Batches[i].Sender, circuit.Batches[i].SenderBefore, circuit.Batches[i].SenderMerkleProof, circuit.AccountRootFlow[2*i], &mimcHash)
verifyMerkleProof(api, circuit.Batches[i].Sender, circuit.Batches[i].SenderAfter, circuit.Batches[i].SenderMerkleProof, circuit.AccountRootFlow[2*i+1], &mimcHash)
verifyMerkleProof(api, circuit.Batches[i].Receiver, circuit.Batches[i].ReceiverBefore, circuit.Batches[i].ReceiverMerkleProof, circuit.AccountRootFlow[2*i+1], &mimcHash)
verifyMerkleProof(api, circuit.Batches[i].Receiver, circuit.Batches[i].ReceiverAfter, circuit.Batches[i].ReceiverMerkleProof, circuit.AccountRootFlow[2*i+2], &mimcHash)
mimcHash.Reset()
var publicKey eddsa.PublicKey
publicKey.A.X = circuit.Batches[i].SenderBefore.PublicKeyX
publicKey.A.Y = circuit.Batches[i].SenderBefore.PublicKeyY
batchTreeNode = append(batchTreeNode, circuit.Batches[i].Message(&mimcHash))
err = eddsa.Verify(curve, circuit.Batches[i].Signature, batchTreeNode[i], publicKey, &mimcHash)
if err != nil {
return err
}
}
api.AssertIsEqual(circuit.AccountRootBefore, circuit.AccountRootFlow[0])
api.AssertIsEqual(circuit.AccountRootAfter, circuit.AccountRootFlow[BatchSize*2])
for i := BatchTreeHeight; i > 0; i-- {
for j, k := 0, 0; j < (1 << i); j, k = j+2, k+1 {
mimcHash.Reset()
mimcHash.Write(batchTreeNode[j], batchTreeNode[j+1])
batchTreeNode[k] = mimcHash.Sum()
}
}
api.AssertIsEqual(batchTreeNode[0], circuit.BatchRoot)
return nil
}
// 驗證交易雜湊證明合法
func verifyMerkleProof(api frontend.API, index frontend.Variable, account Account, merkleProof [AccountTreeHeight]frontend.Variable, merkleRoot frontend.Variable, mimcHash *mimc.MiMC) error {
mimcHash.Reset()
binary := api.ToBinary(index, AccountTreeHeight)
mimcHash.Write(account.PublicKeyX, account.PublicKeyY, account.Balance, account.Nonce)
sum := mimcHash.Sum()
for j := 0; j < AccountTreeHeight; j++ {
mimcHash.Reset()
left := api.Select(binary[j], merkleProof[j], sum)
right := api.Select(binary[j], sum, merkleProof[j])
mimcHash.Write(left, right)
sum = mimcHash.Sum()
}
api.AssertIsEqual(merkleRoot, mimcHash.Sum())
return nil
}
從上面可以發現公開資料便是要丟上鏈進行存證的，所以新的跟舊的交易樹的根雜湊值以及這次的交易樹的根雜湊值必須是公開資料，之後要存在智能合約中，完成好電路之後，便可以將電路的證明鑰匙與驗證鑰匙製造出來，同時也是可以把驗證證明的智能合約丟上鏈並且記下他的合約地址，接下來就只要完成鏈上的合約，ZK Rollup就差不多算大功告成了。
而在鏈上的合約必須要包含著當前帳號樹的根雜湊值，以及累積下來存放的交易樹的根雜湊值，而之前我們知道可以將電路的驗證鑰匙轉換成一個可以驗證證明的智能合約，而在鏈上的這個合約必須要去呼叫驗證的智能合約，一旦驗證成功，就代表著這次打包成功，而呼叫驗證的智能合約要帶入的公開資料中，舊的帳號樹的根雜湊值必須由合約自己帶入，避免被別人透過計算雜湊碰撞來產生假的帳號樹的根雜湊值，所以基本上智能合約就非常簡單。
程式如下：
// SPDX-License-Identifier: MIT
//
pragma solidity ^0.8.0;
interface IVerifyRollupContract {
function verifyProof(
uint256[2] memory a,
uint256[2][2] memory b,
uint256[2] memory c,
uint256[3] memory input
) external view returns (bool);
}
contract ZKRollupContract {
address private owner;
uint256 accountRoot;
uint256[] batchRoot;
IVerifyRollupContract verify;
constructor(uint256 _accountRoot, address _verifyContract) {
owner = msg.sender;
accountRoot = _accountRoot;
verify = IVerifyRollupContract(_verifyContract);
}
function getAccountRoot() external view returns (uint256) {
return accountRoot;
}
function getBatchRoot(uint256 index) external view returns (uint256) {
require(index < batchRoot.length);
return batchRoot[index];
}
function rollup(
uint256[2] memory a,
uint256[2][2] memory b,
uint256[2] memory c,
uint256 newAccountRoot,
uint256 newBatchRoot
) external {
require(msg.sender == owner);
uint256[3] memory input;
input[0] = accountRoot;
input[1] = newAccountRoot;
input[2] = newBatchRoot;
if (verify.verifyProof(a, b, c, input)) {
accountRoot = newAccountRoot;
batchRoot.push(newBatchRoot);
}
}
}
所以我們只需要在鏈下蒐集交易，根據各個不同交易調整帳號樹的狀態，而一旦交易可以填滿交易樹時，就可以透過原本生成出的證明鑰匙產生出證明，只要證明跟著公開資料丟上鏈成功，就代表著鏈上驗證成功，所有人的交易就都在鏈上存證了！
但是在這邊會發現一個問題之前有說過鏈上合約還有一個功能是要做為一個連結鏈上以及鏈下的橋，在這個範例中，只有做到將鏈下的交易打包上鏈而已，所以就代表著一剛開始的錢都只有存在鏈下，並沒有鏈上跟鏈下交互的過程，不過這次示範的便是大部分ZK Rollup的範例，可以在gnark的example中找到類似的，至於要怎麼做到鏈上跟鏈下聯通呢？這又是一門新的學問了，而明天我就來帶大家看看最簡單將鏈上與鏈下連通的方法。
iThome鐵人賽
看影片追技術